Information systems for handling numerous document and data formats are moving towards becoming open systems where different devices are tied to one another to provide versatile solutions to a variety of customer needs. A key factor in these open systems is enabling electronic documents to be printed such that the customer does not perceive any difference between versions printed on different output devices. In order to achieve complete device-independence, efficient methods of accurately altering image resolution without modifying its appearance are required to take advantage of the technology. Hence, raster conversion and enhancement technology, where a bitmap created on or for a first device is altered so as to be printable on a second output device, has become an important aspect of the open system technology.
The present invention is a method for generating resolution conversion/enhancement filters that may be efficiently employed to maintain or improve document appearance, when converting from an original image resolution to an output resolution equal to that of the printing or display device. The filters produced are preferably morphological filters, however template filters may also be generated by the present invention. Compared to template matching filters, morphological filters tend to contain far fewer template patterns (structuring elements), and therefore are much less expensive to implement in a print device. On the other hand, in general, the morphological filter design process is much more complex, and because of the combinatorics involved in the process, the filters are typically restricted to smaller windows, which limit filter goodness. Through the subsampling phase scheme of the present invention, image information is utilized very efficiently, and practical design of relatively high quality, relatively inexpensive, morphological filters is thus enabled.
In the present invention, the resulting image signals may be used to drive devices at the output resolution without negatively impacting spatially sensitive features within the input image. The filters produced using the present invention may be utilized to control a printing device having a scanning beam, where the beam varies in intensity and duration according to the pulses used to control it. As another example, a cathode ray tube uses an electron beam to scan a phosphorous screen. The electron beam may be varied in intensity and duration to accurately display information on the phosphor screen. In both examples, a pulse forming circuit responsive to the output image signal may be used to generate video pulses to control the intensity and operation time of the respective beams.
Mathematical morphology provides a high level, geometric formalism for Boolean logic operations applied to images. It is rooted in set theory, topology, probability, and Minkowski algebra. Although the concepts of morphology hold in N dimensions and are developed for both binary image and gray-scale image operations, the present invention will be described with respect to binary digital images for simplicity. Binary images are treated as a collection of sets (activated, or "black," pixels), and through the Minkowski operations, are operated upon by other sets. The two most primitive morphological operations are erosion and dilation. Two commonly known higher level operations are opening and closing. In the present invention, the morphological operations erosion and dilation are used as they are most relevant to general morphological filtering.
A binary morphological filter is considered to be a very general image mapping: it is a set mapping .PSI. that is increasing [S.OR right.T implies .PSI.(S) .OR right..PSI.(T)] and translation invariant [.PSI.(S+z)=.PSI.(S)+z], where S and T are sets within the image space (referred to herein as images), and z is a point set used here for a position vector. For example, "images S and T" may refer to arbitrary patterns within an image field, such as characters in a document. The definition of morphological filter given here is quite general in that many other filter types are subclasses of morphological filters (For example, order-statistic filters [median, max, rain, etc], and in the gray-scale setting, smoothing convolution filters, and the so-called stack filter are all morphological filters).
In the present invention, binary image processing by morphological filtering employs operations that can be reduced to translations and Boolean operations, and may be implemented at high speeds using parallel architecture hardware. Specifically, erosion can be accomplished by translating S to various positions defined by the structuring element, and then performing a logical AND to combine the translations. Images obtained from independently eroding S by several different structuring elements (which make up the filter basis) are combined using a logical OR (union). As a measure of estimation goodness of the filters, minimum mean-absolute error (MAE) is employed. For binary statistically stationary images, MAE may be interpreted as pixel-count error averaged over the image. For a minimal MAE estimator, the optimal morphological filter minimizes the expected error EQU MAE(.PSI.)=E[.vertline.Y(z)-.PSI.(S')(z).vertline.] (1)
where Y(z) is the desired value of a pixel at z, and .parallel.(S')(z) is the value provided by the morphological filter given observed image S'. Strict-sense stationarity of the image is required for one filter to be optimal throughout the image. This assumption is believed to be reasonably accurate for images of one type. That is, the stationarity condition should be satisfied for an image composed of all text or of all halftone dots.
Previously, various methods and apparatus have been used to alter the resolution of bitmapped images. The following disclosures may be relevant:
U.S. Pat. No. 4,437,122 to Walsh et al. teaches an improved method of converting low resolution images into images of higher resolution for printing so as to simultaneously increase density and smooth character edges. In a CRT display or hardcopy output apparatus, the invention is accomplished by converting an original pixel into a higher resolution 3 x 3 enhanced representation. The status of each of the nine elements in the enhanced representation is determined as a result of an examination of the neighboring pixels of the original pixel.
U.S. Pat. No. 4,544,264 and U.S. Pat. No. 4,625,222, both issued to Bassetti et al. describe enhancement circuits suitable for use in a laser based electrophotographic printing machine. The enhancements are directed at modifying the digital drive signals used to produce the image, including smoothing digitized edges and broadening fine lines in both the horizontal and vertical directions. Leading and trailing edge signals, in both directions are provided to potentially print each black pixel or line as a series of three pixels, a gray leading pixel, overlapped by a central black pixel, which is in turn overlapped by a gray trailing pixel. A similar process is applied for scan lines as well. The series of signals are recombined to effectively control the voltage and current levels of a laser driver.
U.S. Pat. No. 4,690,909 to Bassetti discloses a method and apparatus for enhancing the apparent resolution of electrophotographic printers using a gray dot replacement technique to enhance low resolution output. More specifically, gray or halftone halos are produced along image edges to provide smoothing, while reducing the width of the image regions to avoid thickening thereof as a result of the halo.
U.S. Pat. No. 4,841,375 to Nakajima et al. discloses an image resolution conversion apparatus that converts image data having a predetermined pixel density to a pixel density matching that of a printer so as to enable printing by the printer. The pixel density converter includes: a conversion-pixel position detector for detecting the position of a converted pixel; an original-pixel extractor for extracting a reference original pixel; a conversion-pixel density operation circuit for calculating the density of a conversion pixel; a threshold-value setter for dynamically setting a threshold value; a binary encoding circuit for digitizing the conversion-image density; an input interface for inputting image data; an output interface for outputting image data; and a control circuit for controlling the input/output (I/O) and the conversion operations.
U.S. Pat. No. 4,847,641 and U.S. Pat. No. 5,005,139 to Tung disclose print enhancement circuitry for a laser beam printer. The bit map of a region of the image to be output is compared to a number of patterns or templates. When a match is detected, a section of the bitmap that was matched is replaced with a unique bitmap section designed to compensate for errors. The replacement bitmap section may include predetermined shifting of some dot positions to compensate for the error in the original bitmap section.
U.S. Pat. No. 5,029,108 to Lung teaches an edge enhancement method and apparatus for dot matrix devices wherein a group of gradient mask matrices are applied to a matrix of pixels surrounding a "to be adjusted pixel" so as to determine the existence of an edge and the direction of the brightness change. Once determined, the factors are used to generate a code used to modify the to be adjusted pixel in order to enhance the smoothness of a segment transition.
U.S. Pat. No. 5,134,495 to Frazier et al. discloses a laser-based imaging system that employs a resolution transformation method. The method uses the selective activation in overlapping areas between rasters (scan lines). In one embodiment, a single interleaved pixel, between two scan lines, is formed by the sum of up to six laser pulses at pixel points on adjacent scan lines. In some cases the laser pulses are of insufficient intensity to produce a dot or mark at the point on the scan line where the center of the pulse is received.
U.S. Pat. No. 5,150,311 to Long et al. discloses a system for producing print-dot data suitable for driving a hardcopy printing device. More specifically, the print-dot data is selectively obtained from a conversion operation carried out by a matrix and dot generator combination that respectively generate subtractive color components and a pattern of high resolution print-dots therefrom.
U.S. Pat. No. 5,193,008 to Frazier et al. further describes the resolution enhancement apparatus as one that includes the ability to rasterize the image to be printed at twice the resolution of the printer. The printer then outputs the higher resolution image using an interleaving technique that generates developable dots between scan lines by energizing corresponding dots on adjacent scan lines at a level that will not be developed, but where the overlapping portion of the two corresponding dots will be developable.
U.S. Pat. No. 5,206,741 to Shimura et al. discloses an image processing apparatus for processing image data to be output by a printing unit. A conversion unit converts pixel image data within an image memory into data having a resolution equal to the output resolution of the print mechanism.
U.S. patent application Ser. No. 07/513,415, and the corresponding Japanese laid-open patent publication 4-227584 published Aug. 17, 1992, to Mailloux et al. disclose a method to enable the conversion of binary image data originally generated at a lower resolution into representative binary image data of a higher resolution, wherein the conversion ratio, or magnification factor, is an integer value. Included within the resolution magnification invention are methods for smoothing the interpolated output image and thereby reducing objectionable visual characteristics observable in digitally encoded data using conventional magnification techniques.
A number of the previously described patents and publications are summarized in Torrey Pines Research, Behind Hewlett-Packard's Patent on Resolution Enhancement.TM. Technology, (Becky Colgan ed., BIS CAP International, 1990) pp. 1-60, including concepts associated with resolution enhancement.
James C. Stoffel et al. in A Survey of Electronic Techniques for Pictorial Image Reproduction, IEEE Transactions on Communications, Vol. COM-29, No. 12, December 1981, incorporated by reference for its teachings, discloses image processing algorithms that can be used to transform continuous tone and halftone pictorial image input into spatially encoded representations compatible with binary output processes. A set of image quality and processing complexity metrics are also defined so as to evaluate a number of image processing algorithms with respect to their ability to reproduce continuous tone or halftone pictorial input.
Of particular relevance are the following publications:
Robert P. Loce et al. in Facilitation of Optimal Binary Morphological Filter Design via Structuring Element Libraries and Design Constraints, Optical Engineering, Vol. 31, No. 5, May 1992, pp. 1008-1025, incorporated herein by reference, describes three approaches to reducing the computational burden associated with digital morphological filter design. Although the resulting filter is suboptimal, imposition of the constraints in a suitable manner results in little loss of performance in return for design tractability.
Mathematical Morphology in Image Processing, pp. 43-90 (Edward R. Dougherty ed., Marcel Dekker 1992), hereby incorporated by reference, describes efficient design strategies for the optimal binary digital morphological filter. A suboptimal design methodology is investigated for binary filters in order to facilitate a computationally manageable design process.
Robert P. Loce et al., in Optimal Morphological Restoration: The Morphological Filter Mean-Absolute-Error Theorem, Journal of Visual Communications and Image Representation, (Academic Press), Vol. 3, No. 4, December 1992, pp. 412-432, hereby incorporated by reference, teach expressions for the mean-absolute restoration error of general morphological filters formed from erosion bases in terms of mean-absolute errors of single-erosion filters. In the binary setting, the expansion is a union of erosions, while in the gray-scale setting the expansion is a maxima of erosions. Expressing the mean-absolute-error theorem in a recursive form leads to a unified methodology for the design of optimal (suboptimal) morphological restoration filters. Applications to binary-image, gray-scale signal, and order-statistic restoration on images are included.
Edward R. Dougherty et al., in Optimal mean-absolute-error hit-or-miss filters: morphological representation and estimation of the binary conditional expectation, Optical Engineering, Vol. 32, No. 4, April 1993, pp. 815-827, incorporated herein by reference, disclose the use of a hit-or-miss operator as a building block for optimal binary restoration filters. Filter design methodologies are given for general-, maximum-, and minimum-noise environments and for iterative filters.
Robert P. Loce, in Morphological Filter Mean-Absolute-Error Representation Theorems and Their Application to Optimal Morphological Filter Design, Center for Imaging Science, Rochester Institute of Technology, (Ph.D. Thesis), May 1993, incorporated herein by reference, discloses design methodologies for optimal mean-absolute-error (MAE) morphological based filters.